Lambda the Ultimate

So any ambitious souls out there that have a plan to tackle a new PL for 2006?

It's been a year now since I picked Alice as my language of 2005. I suppose it was a fairly productive year, given that I managed to translate large portions of the first eight chapters of CTM and even brief portions of SICP and TAPL. Though most of that was done in the first six months of the year, and I've had very little time to subsequently move forward.

Having stalled out (what with working two jobs, taking a graduate course in discrete math, and generally helping the kids with 4th grade, 9th grade and college freshman courses), I'll probably carry on with Alice for the new year. Unfortunately, in the present I'm too preoccupied with C# to accomplish much of anything from a conceptual angle.

(via PLNews)
Thoughts on Language Design

Computers with multiple processors are becoming more and more common. We need programming languages that support the use of multiple threads of control. [...] In such a context, the organizing principles of structured programming may not always be appropriate. I'm not talking about avoiding goto. (Java has no goto statement.) I'm talking about sequencing, if-then-else, and loops.

Accelerator: simplified programming of graphics processing units for general-purpose uses via data-parallelism. David Tarditi, Sidd Puri, and Jose Oglesby.

GPUs are difficult to program for general-purpose uses. Programmers must learn graphics APIs and convert their applications to use graphics pipeline operations. We describe Accelerator, a system that simplifies the programming of GPUs for general-purpose uses. Accelerator provides a high-level data-parallel programming model as a library that is available from a conventional imperative programming language. The library translates the data-parallel operations on-the-fly to optimized GPU pixel shader code and API calls.

A library provides programmers with a new type of array, a data-parallel array. Data-parallel arrays differ from conventional arrays in two ways. First, the only operations available on them are aggregate operations over entire input arrays. The operations are a subset of those found in languages like APL. They include element-wise arithmetic and comparison operators, reductions to compute min, max, product, and sum, and transformations on entire arrays. Second, the data-parallel arrays are functional: each operation produces an entirely new data-parallel array.

OS and web search vendors are merging desktop search into their offerings. Vendor solutions vaguely worry me. They seem too focused on the home PC and not on business needs, while needlessly bypassing RDF. There's also vendor lock, bad EULAs, privacy negligence, and lost boundaries between OS, applications, and data - proprietary black boxes tempting us into dependence.

That thinking led me to the open-source Mind Raider program. It's one of the few that makes RDF useful for normal people. It compares to Chandler but focuses less on email and calendars. As far as I know, Chandler doesn't expose RDF or even use it, necessarily. However the Mind Raider Big Picture shows similarity to Chandler's vision.

So why should this stuff matter to LtU. Well, compare formal organization between data that only computers inspect and data that people use daily. Many database systems exist to store data in the former category. Employee and customer address data serves little purpose beyond printing paychecks and shipping labels. A human will not care about values except that they not be empty. Granted that people do use databases to track sales figures and other aggregates. Still even those folks use data in the latter category: stray thoughts and reminders, sticky notes, social and business correlations, restaurant napkin sketches, collaborative data, recorded conversations, news clippings. A large cloud of miscellany doesn't rise to the level of application documents or the formality of enterprise systems.

Few systems exist to aggregate and organize that stuff. If your brain suffices, then good for you. The rest of us need a crutch. Some people use spreadsheets to store lists simply because there's little else available. I've used software which imitates sticky notes on screen. It leaves much to be desired. There are dozens of little programs for narrow data types - address books, internet bookmark apps, password managers, photo albums, etc. How do you tell the address book that the photo album has pictures of the guy, and that his web link lives in the bookmark manager? Right now, you don't. And programs never organize data just the way you want. Besides, exceptions to the common format always arise. So the problem is not just searching documents and email, nice as that is, but organizing human details in useful ways. Moleskin notebooks and Dictaphones have been around a long while. It's time for cool software.

Somehow RDF seems primed for the role, but it needs less abstract public relations. Raw RDF may not be the ideal presentation but still seems a likely candidate for the underlying data model. Each individual develops a personal ontology (aka "working style" if you will) over years of time. RDF can capture that, but it will take friendly programs like Mind Raider. What do you think?

Yes, a new study about Sapir-Whorf,

The researchers said the findings supported the Whorf hypothesis, but only in the right visual field.

Report co-author Aubrey Gilbert said: "Previous studies addressing the possible influence of language on perception have tended to look for a simple yes or no answer to the question.

"Our findings suggest a more complex picture, based on the functional organisation of the brain."

This is by no means the last word on this fascinating subject...

An Operational Foundation for Delimited Continuations in the CPS Hierarchy

We present an abstract machine and a reduction semantics for the lambda-calculus extended with control operators that give access to delimited continuations in the CPS hierarchy. The abstract machine is derived from an evaluator in continuation-passing style (CPS); the reduction semantics (i.e., a small-step operational semantics with an explicit representation of evaluation contexts) is constructed from the abstract machine; and the control operators are the shift and reset family. We also present new applications of delimited continuations in the CPS hierarchy: finding list prefixes and normalization by evaluation for a hierarchical language of units and products.

...or in other words - a view on the delimited continuations from another side (as compared to "A Monadic Framework for Subcontinuations" or Oleg's posts on Hakell list). I find it useful to learn about the same concept from different sources - and the delimited continuations are still promising to become an important concept.

Also, I suspect that defunctionalized approach might be more straightforward for people coming from imperative languages.

I have been teaching programming for nearly ten years now, to university students from the first to the fourth year, to both CS majors and non-CS majors (all in technical fields). I have tried to distill results from programming language research into these courses (and wrote a book in the process, CTM). Recently, I had two insights:

1. The best year in which to teach a programming course based on programming concepts is the second year. In the first year, students are not mature enough. In the third and later years, students get conservative. In the second year, they have enough maturity to understand the concepts and enough openness to appreciate them. At UCL, we have been doing this for two years now for all engineering students (more than 300 in Fall 2005) using a first-year course based on Java, and it works remarkably well (better than I expected).

2. Students can be taught programming semantics in the second year. This can succeed if: (1) the semantics requires very little mathematical baggage, just sets and functions, (2) the semantics is factored so it can be taught incrementally, and (3) the semantics is simple and uncluttered so that students can work out a program's execution with paper and pencil. The semantics of CTM is one example that fits these conditions. The students consider the semantics the hardest part of the course. I think it's because they've never been exposed to this kind of formalism, so they are a bit unsettled by it. But I am convinced that students in any technical field should be taught programming language semantics at least once in their careers. It should be as basic as algebra or calculus.

What do you think? I would appreciate hearing your experience and comments. Here are the course notes of the latest version of my course (they are in French; there are English course notes too but they are not as nice for the second year).

Thinking about teaching our undergraduate PL next semester, I've been digging up lots of suddenly interesting readings. The teaching about PL project links to much information, and Wadler's and Felleisen et al.'s critiques of SICP were enlightening as well.

Most recently I stumbled upon Joseph Bergin's writings on teaching, in particular ""The undergraduate language course: what to do?" (SIGPLAN Notices 36(6):20-22, 2001), which describes a taxonomy of course approaches: "historical", "smorgasbord", "interpreter", and "principles". Also relevant is a recent article "In Computer Science, A Growing Gender Gap: Women Shunning a Field Once Seen as Welcoming" by Marcella Bombardieri (Boston Globe 2005-12-18).

(I'm sorry I couldn't find Wadler's and Bergin's articles freely available online.)

A nice paper apropos of tail calls and exceptions:

Nick Benton and Andrew Kennedy. 2001. Exceptional syntax. Journal of Functional Programming 11(4): 395-410.

From the points of view of programming pragmatics, rewriting and operational semantics, the syntactic construct used for exception handling in ML-like programming languages, and in much theoretical work on exceptions, has subtly undesirable features. We propose and discuss a more well-behaved construct.

As the year winds down, the programming language news keeps flowing; at this point I wouldn't be surprised by major New Year’s Eve announcements...

It seems we are not keeping up with the latest news.